# -*- coding: utf-8 -*-            
# @Time : 2023/5/24 22:24
# @Author  : lining
# @FileName: 括号生成.py
"""
https://leetcode.cn/problems/generate-parentheses/
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
乘法原理
"""

x = {}
def fun(n):
    """
    s=(A)B    (A)为一个整体    A为k-1对括号，则B为n-k对括号
    n = 3 k =1 n-k=2   ()()()   ()(())
    :param n: 生成括号的对数
    :return: 列表，列表内容是组成的括号
    """
    # 0对返回空列表
    if n == 0:
        return ['']
    result = [] # 要初始在方法内，每一次递归都生成一个新的result
    print(id(result))
    for k in range(1, n+1):
        print(f'k={k}')
        A = fun(k-1)
        print(f'A={str(A)}')
        B = fun(n-k)
        print(f'B={str(B)}')
        for a in A:
            for b in B:# result初始化在外面，B一直在增加元素，会陷入死循环
                result.append(f'({a}){b}')
    return result

x = fun(11)
print(x)

store = {}
class Solution:
    # 分治解法
    def generateParenthesis(self, n: int):
        if n == 0:
            return [""]
        if n in store:
            return store[n] # 记忆化
        ans = []
        for k in range(1, n + 1): # 加法原理
            A = self.generateParenthesis(k - 1)
            B = self.generateParenthesis(n - k)
            # S=(A)B
            # 乘法原理
            for a in A:
                for b in B:
                    ans.append("(" + a + ")" + b)
        store[n] = ans
        return ans

# a = Solution().generateParenthesis(2)
# print(a)

